#include<stdio.h>
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    if (headA == NULL || headB == NULL)
        return NULL;
    struct ListNode* tailB = headB;
    while (tailB->next != NULL)
    {
        tailB = tailB->next;
    }
    tailB->next = headA;
    struct ListNode* slow = headB;
    struct ListNode* fast = headB;
    int hasCycle = 0;
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            hasCycle = 1;
            break;
        }
    }
    if (hasCycle)
    {
        slow = headB;
        while (slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        if (slow)
        {
            tailB->next = NULL;
            return slow;
        }
    }
    tailB->next = NULL;
    return NULL;
}


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* list1 = headA;
    struct ListNode* list2 = headB;
    int a = 0, b = 0;
    while (list1)
    {
        list1 = list1->next;
        a++;
    }
    while (list2)
    {
        list2 = list2->next;
        b++;
    }
    struct ListNode* longhead = headA;
    struct ListNode* shorthead = headB;
    int len = abs(a - b);
    if (a < b)
    {
        longhead = headB;
        shorthead = headA;
    }
    while (len)
    {
        longhead = longhead->next;
        len--;
    }
    while (longhead != shorthead)
    {
        longhead = longhead->next;
        shorthead = shorthead->next;
    }
    return longhead;
}